{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.9-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3.7.9 64-bit",
   "metadata": {
    "interpreter": {
     "hash": "0600588c3b5f4418cbe7b5ebc6825b479f3bc010269d8b60d75058cdd010adfe"
    }
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "source": [
    "`pop()`从列表末尾移除元素，O(1)  \n",
    "`pop(i)`从列表中部移除元素，O(n)\n",
    "因为`pop(i)`要删除元素，并把后面的值向前移。这样能是按索引取/赋值更快，达到O(1) -> tradeoff"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "popzero = timeit.Timer(\"x.pop(0)\", \"from __main__ import x\")\n",
    "popend = timeit.Timer(\"x.pop()\", \"from __main__ import x\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = list(range(int(2e4)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "popzero:  0.15031270000002905\npopend: 0.00010059999999612046\n"
     ]
    }
   ],
   "source": [
    "print(\"popzero: \", popzero.timeit(number=1000))\n",
    "print(\"popend:\", popend.timeit(number=1000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "         pop(0)           pop()\n",
      "        0.00024,         0.00560\n",
      "        0.00024,         0.02048\n",
      "        0.00027,         0.02088\n",
      "        0.00024,         0.03297\n",
      "        0.00021,         0.03609\n",
      "        0.00012,         0.03367\n",
      "        0.00008,         0.03346\n",
      "        0.00011,         0.03725\n",
      "        0.00009,         0.03990\n",
      "        0.00014,         0.05913\n"
     ]
    }
   ],
   "source": [
    "print(\"pop(0)\".rjust(15), \"pop()\".rjust(15))\n",
    "for i in range(int(1e3), int(1e4 + 1), int(1e3)):\n",
    "    x = list(range(i))\n",
    "    pt = popend.timeit(number=1000)\n",
    "    x = list(range(i))\n",
    "    pz = popzero.timeit(number=1000)\n",
    "    print(\"{:15.5f}, {:15.5f}\".format(pt, pz))"
   ]
  }
 ]
}